116. 填充每个节点的下一个右侧节点指针

#leetcode/tree/traversal/linear

116. 填充每个节点的下一个右侧节点指针

Similar Question

leading to the advanced question

Solution Tips

第一想法是依赖 depth, 其实是不依赖的

方案一: BFS

  const {BST} = require('./utils/structure/BST')
  const bst = new BST()
  bst.insert(1)
  bst.insert(2)
  bst.insert(3)
  bst.insert(4)
  bst.insert(5)
  bst.insert(6)
  bst.insert(7)
  
  
  var connect = function(root) {
    const level = []
    preorder(root,0,level)
    level.forEach((subQueue) => {
      subQueue.forEach((node,index,subQueue) => {
        if(node!==null) node.next = subQueue[index+1] || null
      })
    })
    return root
  
    function preorder(node,depth,level){
      if(depth>level.length-1) level.push([])
  
      if (node === null) {
        level[depth].push(node)
      } else {
        level[depth].push(node)
        preorder(node.left, depth + 1, level)
        preorder(node.right, depth + 1, level)
      }
    }
  }
  console.log(connect(bst.root()))

var connect = function(root) {
    if (root === null) {
        return root;
    }
    
    // 初始化队列同时将第一层节点加入队列中，即根节点
    const Q = [root]; 
    
    // 外层的 while 循环迭代的是层数
    while (Q.length > 0) {
        
        // 记录当前队列大小
        const size = Q.length;
        
        // 遍历这一层的所有节点
        for(let i = 0; i < size; i++) {
            
            // 从队首取出元素
            const node = Q.shift();
            
            // 连接
            if (i < size - 1) {
                node.next = Q[0];
            }
            
            // 拓展下一层节点
            if (node.left !== null) {
                Q.push(node.left);
            }
            if (node.right !== null) {
                Q.push(node.right);
            }
        }
    }
    
    // 返回根节点
    return root;
};

方案二: 递归 + 不依赖 Depth

  const {BST} = require('./utils/structure/BST')
  const bst = new BST()
  bst.insert(1)
  bst.insert(2)
  bst.insert(3)
  bst.insert(4)
  bst.insert(5)
  bst.insert(6)
  bst.insert(7)
  
  
  var connect = function(root) {
    const level = []
    preorder(root,0,level)
    level.forEach((subQueue) => {
      subQueue.forEach((node,index,subQueue) => {
        if(node!==null) node.next = subQueue[index+1] || null
      })
    })
    return root
  
    function preorder(node,depth,level){
      if(depth>level.length-1) level.push([])
  
      if (node === null) {
        level[depth].push(node)
      } else {
        level[depth].push(node)
        preorder(node.left, depth + 1, level)
        preorder(node.right, depth + 1, level)
      }
    }
  }
  console.log(connect(bst.root()))